Various software methods are known for identifying optimal solutions to complicated problems. Some methods use genetic algorithms to identify various solutions. Genetic algorithms may be used to resolve any problem having parameters that define the scope of the problem and solution criteria used to judge the solution. Genetic algorithms may be used, for example, in an application for laying out an integrated circuit, where various layout solutions are possible. The algorithm may, for example, determine where components or cells of components should be positioned to achieve optimal utilization of chip area.
Genetic algorithms start with one or more populations of potential solutions, also referred to as chromosomes or genes. The initial populations may be generated, for example, at random. Within the population, these solutions are compared with other solutions to create new solutions, hopefully resulting in better solutions. The process of combining solutions is referred to as “cross-over” or “cross-breeding” because the resulting “offspring” solutions have characteristics of one or more “parent” solutions used in cross-over. Cross-over creates a variety of solutions that may be more or less optimal than their parent solutions. Offspring solutions may also be created by other methods of modifying the solutions, referred to as “mutation.”
The offspring may be combined with the parent population, from which optimal solutions may be identified during a process of “competition,” also referred to as “selection.” Selection may simply remove less optimal solutions from the population. An example method may include several iterations of cross-over and selection, such that several generations of solutions are generated for the population. During this example process, mutations may occur to introduce more beneficial traits into the population. In one example, multiple populations may separately use this same process to create multiple solutions.
In existing methods, the offspring within a population tend to look very similar. The process of intra-population is overly degenerative, thereby causing a lack of diversity in the resulting solutions. Because of this lack of diversity, the solution generated by a population tends to be optimal only with respect to similar solutions and may not be optimal when considered in context of the entire problem. Mutation may provide some diversity, but does not solve the problem. Another method of creating diversity is to retain less optimal solutions during the process of competition. The problem with this method is that it keeps potentially bad solutions in the population and still results in less optimal solutions. What is needed is an improved genetic algorithm for identifying optimal solutions. In particular, what is needed is a method for introducing greater diversity into a genetic algorithm.